#pragma once

#include<vector>
#include<iostream>
using namespace std;

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            for (int j = i + 1; j < nums.size(); ++j)
            {
                for (int k = j + 1; k < nums.size(); ++k)
                {
                    for (int u = k + 1; u < nums.size(); ++u)
                    {
                        vector<int> v{ nums[i] , nums[j] , nums[k] , nums[u] };
                        if (nums[i] + nums[j] + nums[k] + nums[u] == target && find(ret.begin(), ret.end(), v) == ret.end())
                        {
                            ret.push_back(v);
                        }
                    }
                }
            }
        }
        return ret;
    }

    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());

        int a = 0, b = 0, c = 0, d = 0;
        while (a < nums.size())
        {
            long long int value = target - nums[a];
            b = a + 1;
            c = b + 1;
            d = nums.size() - 1;
            while (b < nums.size())
            {
                c = b + 1;
                d = nums.size() - 1;
                long long int val = value - nums[b];
                while (c < d)
                {
                    if (nums[c] + nums[d] > val)
                    {
                        --d;
                    }
                    else if (nums[c] + nums[d] < val)
                    {
                        ++c;
                    }
                    else
                    {
                        ret.push_back({ nums[a] , nums[b] , nums[c] , nums[d] });
                        ++c;
                        while (c < d && nums[c] == nums[c - 1])
                        {
                            ++c;
                        }
                        --d;
                        while (d > c && nums[d + 1] == nums[d])
                        {
                            --d;
                        }
                    }
                }
                ++b;
                while (b < c && nums[b] == nums[b - 1])
                {
                    ++b;
                }
            }
            ++a;
            while (a < b && nums[a] == nums[a - 1])
            {
                ++a;
            }
        }
        return ret;
    }
};